3. 数据结构-链表

链表

​ 链表存储有序的元素的集合,但是和数组不同的是,链表中的元素在内存中的存储并不是连续的.每一个链表元素都包含了一个存储元素本身的节点和一个指向下一个元素的引用.

​ 但是相对于传统的数组,链表的一个好处就是增删的时候无需移动其他元素,只要更改指针的指向就可以了.但是缺点就是如果想要访问链表中的元素,需要从头开始循环迭代到你想要的元素.
链表需要实现的几个方法:

1. apped(element),向列表尾部添加一个新元素,注意这里所指的列表并不是我们想象中的有序列表,链表是无序的.
2. insert(position,element),在链表的指定位置插入一个新的元素.
3. remove(element),从链表中删除一项.
4. indexOf(element),返回该元素在列表中的索引,如果列表中没有该元素就返回-1.
5. removeAt(position),从列表的指定位置移除元素.
6. isEmpty(),判断该链表是否为空.
7. size(),返回该链表包含的元素个数.
8. toString(),返回链表元素的字符串值.

// 下面的所有的注释所解释的语句都是注释下面的语句。以下所有的“节点元素”都代表node
function LinkedList() {
  //node才是链表中的单独元素，但是这个元素中又包含自身的值和指向下一个node的指针
  let Node = function (element) {
    //node的自身元素
    this.element = element;
    /* 
        这个next要特别注意，它在理论上是指向链表下一个节点元素的指针，但是在js的实现中，其实这个指针不过是一个对象的索引，而这个索引所包含的就是下一个node
        就像是这样{element:1,next:{element,next:{element:3,next...}}}，这种对象的一层层嵌套，这样也可以解释了为什么在中间插入链表元素时，
        需要一层一层的迭代到需要插入的位置。
      */
    /*
        换句话说，这里的next指针，指向的是下一个node节点元素的整体，不单单只是node中的element元素。
      */
    this.next = null;
  };

  let length = 0; //链表长度初始化
  let head = null; //在链表中，我们需要存储第一个节点元素的引用，也就是head，在没有节点元素的时候初始化为null。
  // append方法类似于js数组的push，向链表的尾部添加节点元素。
  // 在append方法中有两种情况，一种是没有节点元素，链表的长度是0，另一种是已经存在了至少一个节点元素，应对这两种不同的情况会有不同的操作。
  this.append = function (element) {
    //声明变量，append添加的element应该是node，所以通过Node类进行包装
    let node = new Node(element);
    //这里就存在了一个问题，那么就是我们在给链表添加节点元素的时候只有head的引用，也就是我们只知道head是什么，但是其他的我们一概不知。
    //所以这里声明一个current变量，用来存储我们当前的节点是什么。
    let current;
    //这里，如果head是null，说明该链表是没有节点元素的，因为有节点元素的话head不可能为null（head会指向第一个节点元素），那么既然如此，我们的head=node就可以了。
    //还有，这里的“=”，实在是让人很迷茫，既然是指针，为什么要“赋值”？
    //因为无论是head、node.next(链表节点元素的指针)还是current还是下面会声明的previous。都是存储当前位置信息的一个存储器。
    //也就是说，这些变量所代表的是一个值信息的存储，他们存储的值代表他们所指向的节点元素。
    //嗯，，，，希望我说明白了。。。。
    console.log(head); //你可以看到head以及链表在js中展现大概是什么样的。
    if (head === null) {
      head = node;
    } else {
      //这里，如果head！=null，说明该链表至少有一个节点元素，那么当前的current自然就是head，因为我们要从head开始迭代到结尾。
      current = head;
      //这里容易让人疑惑的地方是current.next是啥?
      //上面current已经是head了，那么无论是只有一个节点元素还是多个节点元素，最后一个节点元素的next必为null，别问我为啥了。
      //所以这里只要current.next不为null（也就是有实际意义的值），那么就循环到current.next是null为止。
      //因为只有这样才说明当前的current是链表中的最后一个节点元素
      while (current.next) {
        current = current.next;
      }
      //既然我们找到了链表中的最后一个节点元素，那么把该节点元素的next=node就好了。
      //那么这里还要说的是，每一个新node的next必然是null，嗯，就是这么定义的，没有为啥。
      //所以在我们将current.next指向node的时候，链表最后一个节点元素的指向自然就是null了。
      current.next = node;
    }
    // 嗯...别忘了增加一个单位长度
    length++;
  };
  // 在链表的任意“合法”位置插入节点元素,position代表要插入的位置，element不多说，代表要插入的元素。
  this.insert = function (position, element) {
    // 这个判断比较有趣，如果position小于0并且大于该链表的长度，说明这个position不合法。直接返回false
    //如果在大于等于0并且小于等于length，OK，插入位置合法，继续...
    if (position >= 0 && position <= length) {
      //同样的，要建个node
      let node = new Node(element),
        // 同样的，当前的current是head
        current = head,
        // 新增了一个previous，这个previous是为了衔接需要插入的节点元素的。
        previous,
        // 这个index不是length，它是为了记录限定循环的计数器，作用类似于current和previous。
        index = 0;
      // 这里，如果position是0，意味着我要在头部插入元素。
      if (position === 0) {
        // 那么自然，新建的节点元素的指针（next）就指向了当前元素。而head自然就是新建的节点元素（node）了。
        node.next = current;
        head = node;
      } else {
        // 那么如果想要在除了第一个元素的其他位置插入元素。
        // 在没有到达想要插入的位置的时候，我们需要迭代替换previous和current，使其依次的往后移动。
        while (index++ < position) {
          //这里就是每一次的移动，前一个等于当前，当前的又变成了下一个（就这样依次移动到指定的position位置）
          previous = current;
          current = current.next;
        }
        //那么在到达了这个位置后，我们需要把新建的node节点元素插入近previous和current。
        //也就是改变node节点元素和previous的指针。使node节点元素指向当前的current。而previous的指针指向node。
        //这样也就完成了节点元素在指定位置的插入
        node.next = current;
        previous.next = node;
      }
      //插入成功，长度增加一个单位并返回true
      length++;
      return true;
    } else {
      return false;
    }
  };
  // 这个方式是移除制定位置的节点元素。
  this.removeAt = function (position) {
    //同样的合法值范围限制。
    if (position > -1 && position < length) {
      //同样的变量声明。
      let current = head,
        previous,
        index = 0;
      //这里比较有趣，如果是要移除第一个节点元素，那么直接把head的指针指向当前节点元素（current）的下一个（.next）就可以了。
      //因为我们中断了head和current的链接，直接使current不存在于链表中了，这样我们无论如何迭代都获取不到此时的current。
      //这样操作之后，我们只要等待js垃圾回收器回收它就好了。
      if (position === 0) {
        head = current.next;
      } else {
        //同样的迭代移动
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        //这里我们迭代到了我们想要移除的元素的位置，同样中断了current的在链表中的链接。也就删除了该节点元素
        previous.next = current.next;
      }
      //长度减少一个单位。
      length--;
      //返回删除的元素值
      return current.element;
    } else {
      return null;
    }
  };
  //获取该元素在链表中的位置
  this.indexOf = function (element) {
    let current = head,
      index = 0; //不解释了，这里index为0，因为要从链表的第一个0位开始遍历
    //那么这里又比较有趣了，这里的current无非两种情况，null或者一个具体的值。
    //如果是null，说明该链表是空的，不然current=head不可能为null
    //如果不为null，继续判断
    while (current) {
      //那么如果current不为null，并且如果element和current的element相等。说明找到了，直接返回index
      if (element === current.element) {
        return index;
      }
      //这里其实可以是为上面if判断的else分支，如果不相等，那么计数器index就加一个单位，并且current指针往后移动。
      index++;
      current = current.next;
    }

    return -1;
  };
  // 我们既然有了indexOf和removeAt，这个remove方法我就不多说了。
  this.remove = function (element) {
    let index = this.indexOf(element);
    console.log(index);
    return this.removeAt(index);
  };
  // 下面的方法也都很简单，无需多说
  this.isEmpty = function () {
    return length === 0;
  };
  this.size = function () {
    return length;
  };
  this.getHead = function () {
    return head;
  };
  this.toString = function () {
    let current = head,
      string = "";

    while (current) {
      string += current.element + (current.next ? "n" : "");
      current = current.next;
    }

    return string;
  };
  this.print = function () {
    console.log(this.toString());
  };
}

var list = new LinkedList();

list.append(1);
list.append(2);
list.append(3);
list.append(4);
list.append(5);
list.print(); //1n2n3n4n5
list.insert(2, 99);
list.print(); //1n2n99n3n4n5
list.removeAt(1);
list.print(); //2n3n4n5

双向链表

在基础链表之外，还有双向链表和循环链表和双向循环链表。链表和循环链表的唯一的区别在于，最后一个元素指向下一个元素的指针不是 null，而是 head。

其实循环链表只能从头到尾的循环，而双向循环链表可以两个方向循环，想怎么玩怎么玩。

其实简单说双向链表与链表的区别就在于，双向链表不仅仅有一个指向下一个节点元素的指针，还同时拥有一个指向上一个节点元素的指针。前后都可以链接，故，称之为双向链表。

​ 那么既然是双向的指针，所以我们的代码需要新增一些东西。

function DoublyLinkedList() {
  let Node = function (element) {
    this.element = element;
    this.next = null;
    //在双向链表中，这里多了个指向前一个节点元素的指针prev
    this.prev = null;
  };

  let length = 0;
  let head = null;
  //同样的这里多了一个保存链表最后一项节点的引用变量，为什么要加这个变量？
  //因为是双向链表，普通链表只能从头到尾的迭代各节点元素，一方面是因为普通链表中只有一个存储头部节点元素的head变量。
  //但是双向链表可以从尾部开始迭代，这就是tail的意义。
  let tail = null;
}

这就是双向链表的类的变动（不包括其中的方法），我们可以看到只是多了 node 节点元素中 prev（前一个）节点元素的指针，还有 tail 变量对尾部节点元素的引用。

那么下面我们来看看 insert 方法的变化。

//我们来看看双向链表中insert方法,普通链表中，我们只需要控制next指针就可以了，但是在双向链表中，在控制next指针的同时，我们还要控制prev指针
this.insert = function (position, element) {
  //在普通链表中在任意位置添加元素有两种情况，一个是添加到头部，另外一个是除了头部以外的其他位置，
  //在双向链表中除了这两种情况，还多了一种，添加在链表尾部
  if (position >= 0 && position <= length) {
    let node = new Node(element);
    let current = head;
    let previous;
    let index = 0;
    //添加到头部的情况
    if (position === 0) {
      //这里，如果head为null，也就是说该链表是没有任何节点元素的情况，那么加入的这个节点元素在链表中是唯一的
      //所以，head引用为node，tail的引用也为node
      if (!head) {
        head = node;
        tail = node;
        //那么如果，head不为null，说明链表中存在至少一个元素。
      } else {
        //由于current就是head，那么要插入节点元素的话只要把node的next指针指向current，就说明我们在current前面插入了该节点元素。
        node.next = current;
        //因为是双向列表，我们还要给current.prev一个指向。
        current.prev = node;
        //那么既然我们在current前面插入了元素，这里也就要改变head的引用，变为我们插入的node
        head = node;
      }
      //如果我们想要插入尾部的情况
    } else if (position === length) {
      //这里稍微有趣一点，这里我们要在尾部加入元素，不用像普通链表那样迭代到最后一项再操作。
      //我们只需要把current直接置为tail的引用就可以了，方便快捷
      current = tail;
      //那么我们已经拿到了最后一项节点元素的引用并且设置为了current。
      //我们只需要把current（tail）的next指向node节点元素，并且把node的prev只想current。
      //其实就是说，current节点的next指针不再是null了，因为我们在它的后面增加了一个“插入元素”，所以它的next指针为node
      //而此时node的prev指针也就理所当然的指向了current。
      current.next = node;
      node.prev = current;
      //插入元素完成，但是我们此时的tail其实是current不是node，所以更改一下tail的引用。
      tail = node;
    } else {
      while (index++ < position) {
        //依次往后移动...不多说
        previous = current;
        current = current.next;
      }
      //在移动到需要插入节点元素的位置时。
      //我们要插入在current的前面，自然就会有下面的结果了
      node.next = current;
      previous.next = node;
      //但是我们由于是双向链表，我们不仅仅要修改next指针，还要修改prev指针
      current.prev = node;
      node.prev = previous;
    }
    length++;
    return true;
  } else {
    return false;
  }
};

其实 insert 方法在双向链表中，只是多了一种尾部情况的判断以及 prev 指针的改变，注释已经说的很详细了，不多说废话，我们继续看看 removeAt 方法在双向链表中的实现。

this.removeAt = function (position) {
  if (position > -1 && position < length) {
    let current = head,
      previous,
      index = 0;

    if (position === 0) {
      head = current.next;
      if (length === 1) {
        tail = null;
      } else {
        head.prev = null;
      }
    } else if (position === length - 1) {
      current = tail;
      tail = current.prev;
      tail.next = null;
    } else {
      while (index++ < position) {
        previous = current;
        current = current.next;
      }

      previous.next = current.next;
      current.next.prev = previous;
    }

    length--;
    return current.element;
  } else {
    return null;
  }
};